package gold.digger;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC923 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int threeSumMulti(int[] A, int target) {
            int MOD = 1_000_000_007;
            long[] count = new long[101];
            for (int x : A)
                count[x]++;

            long ans = 0;

            // All different
            for (int x = 0; x <= 100; ++x)
                for (int y = x + 1; y <= 100; ++y) {
                    int z = target - x - y;
                    if (y < z && z <= 100) {
                        ans += count[x] * count[y] * count[z];
                        ans %= MOD;
                    }
                }

            // x == y != z
            for (int x = 0; x <= 100; ++x) {
                int z = target - 2 * x;
                if (x < z && z <= 100) {
                    ans += count[x] * (count[x] - 1) / 2 * count[z];
                    ans %= MOD;
                }
            }

            // x != y == z
            for (int x = 0; x <= 100; ++x) {
                if (target % 2 == x % 2) {
                    int y = (target - x) / 2;
                    if (x < y && y <= 100) {
                        ans += count[x] * count[y] * (count[y] - 1) / 2;
                        ans %= MOD;
                    }
                }
            }

            // x == y == z
            if (target % 3 == 0) {
                int x = target / 3;
                if (0 <= x && x <= 100) {
                    ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
                    ans %= MOD;
                }
            }

            return (int) ans;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC923 an = new LC923();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
